#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;


bool binarySearch(const vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

	while (left<=right)
	{
		int mid = left + (right - left) / 2;
		if (nums[mid] == target) {
			return true;
		}
		else if (nums[mid] > target) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	return false;
}


void sort(vector<int>& nums,int left,int right) {
	if (left >= right)return;
	
	int beg = left;
	int end = right;

	int pivot = nums[(left + right) / 2];

	while (beg<=end)
	{
		while (beg <= end&&nums[beg]< pivot) {
			beg++;
		}

		while (beg <= end && nums[end] > pivot) {
			end--;
		}

		if (beg <= end) {
			swap(nums[beg], nums[end]);
			beg++;
			end--;
		}

	}

	sort(nums, left, end);
	sort(nums, beg, right);
}
